package org.niu.dfs;

import java.util.*;

public class PermuteUnique {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        List<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[num.length];
        backtracking(num,list,visited);
        return ans;
    }

    void backtracking(int[] num, List<Integer> list,boolean[] visited){
        if(list.size() == num.length){
            if(!ans.contains(list)){
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if(!visited[i]){
                visited[i] = true;
                list.add(num[i]);
                backtracking(num,list,visited);
                list.remove(list.size()-1);
                visited[i] = false;
            }
        }
    }
}
